mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, symbolic dynamics is the practice of modeling a topological or smooth

dynamical system In mathematics, a dynamical system is a system in which a Function (mathematics), function describes the time dependence of a Point (geometry), point in an ambient space. Examples include the mathematical models that describe the swinging of a ...

by a discrete space consisting of infinite

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...

s of abstract symbols, each of which corresponds to a

state State may refer to: Arts, entertainment, and media Literature * ''State Magazine'', a monthly magazine published by the U.S. Department of State * ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States * ''Our S ...

of the system, with the dynamics (evolution) given by the

shift operator In mathematics, and in particular functional analysis, the shift operator also known as translation operator is an operator that takes a function to its translation . In time series analysis, the shift operator is called the lag operator. Shift o ...

. Formally, a

Markov partition A Markov partition in mathematics is a tool used in dynamical systems theory, allowing the methods of symbolic dynamics to be applied to the study of hyperbolic dynamics. By using a Markov partition, the system can be made to resemble a discrete ...

is used to provide a

finite cover In mathematics, and more particularly in set theory, a cover (or covering) of a set X is a collection of subsets of X whose union is all of X. More formally, if C = \lbrace U_\alpha : \alpha \in A \rbrace is an indexed family of subsets U_\alpha\s ...

for the smooth system; each set of the cover is associated with a single symbol, and the sequences of symbols result as a trajectory of the system moves from one covering set to another.

History

The idea goes back to

Jacques Hadamard Jacques Salomon Hadamard (; 8 December 1865 – 17 October 1963) was a French mathematician who made major contributions in number theory, complex analysis, differential geometry and partial differential equations. Biography The son of a teac ...

's 1898 paper on the

geodesic In geometry, a geodesic () is a curve representing in some sense the shortest path ( arc) between two points in a surface, or more generally in a Riemannian manifold. The term also has meaning in any differentiable manifold with a connection. ...

s on

surface A surface, as the term is most generally used, is the outermost or uppermost layer of a physical object or space. It is the portion or region of the object that can first be perceived by an observer using the senses of sight and touch, and is ...

s of negative

curvature In mathematics, curvature is any of several strongly related concepts in geometry. Intuitively, the curvature is the amount by which a curve deviates from being a straight line, or a surface deviates from being a plane. For curves, the canonic ...

. It was applied by

Marston Morse Harold Calvin Marston Morse (March 24, 1892 – June 22, 1977) was an American mathematician best known for his work on the ''calculus of variations in the large'', a subject where he introduced the technique of differential topology now known a ...

in 1921 to the construction of a nonperiodic recurrent geodesic. Related work was done by Emil Artin in 1924 (for the system now called

Artin billiard In mathematics and physics, the Artin billiard is a type of a dynamical billiard first studied by Emil Artin in 1924. It describes the geodesic motion of a free particle on the non-compact Riemann surface \mathbb/\Gamma, where \mathbb is the u ...

Pekka Myrberg Pekka Juhana Myrberg (30 December 1892, Viipuri – 8 November 1976, Helsinki) was a Finnish mathematician known for developing the concept of period-doubling bifurcation in a paper published in the 1950s. The concept was further developed by Mitc ...

Paul Koebe Paul Koebe (15 February 1882 – 6 August 1945) was a 20th-century German mathematician. His work dealt exclusively with the complex numbers, his most important results being on the uniformization of Riemann surfaces in a series of four papers in ...

Jakob Nielsen Jacob or Jakob Nielsen may refer to: * Jacob Nielsen, Count of Halland (died c. 1309), great grandson of Valdemar II of Denmark * , Norway (1768-1822) * Jakob Nielsen (mathematician) (1890–1959), Danish mathematician known for work on automorphi ...

G. A. Hedlund Gustav Arnold Hedlund (May 7, 1904 – March 15, 1993), an American mathematician, was one of the founders of symbolic and topological dynamics. Biography Hedlund was born May 7, 1904, in Somerville, Massachusetts. He did his undergraduate studi ...

. The first formal treatment was developed by Morse and Hedlund in their 1938 paper.

George Birkhoff George David Birkhoff (March 21, 1884 – November 12, 1944) was an American mathematician best known for what is now called the ergodic theorem. Birkhoff was one of the most important leaders in American mathematics in his generation, and during ...

Norman Levinson Norman Levinson (August 11, 1912 in Lynn, Massachusetts – October 10, 1975 in Boston) was an American mathematician. Some of his major contributions were in the study of Fourier transforms, complex analysis, non-linear differential equation ...

and the pair

Mary Cartwright Dame Mary Lucy Cartwright, (17 December 1900 – 3 April 1998) was a British mathematician. She was one of the pioneers of what would later become known as chaos theory. Along with J. E. Littlewood, Cartwright saw many solutions to a problem ...

and

J. E. Littlewood John Edensor Littlewood (9 June 1885 – 6 September 1977) was a British mathematician. He worked on topics relating to mathematical analysis, analysis, number theory, and differential equations, and had lengthy collaborations with G. H. H ...

have applied similar methods to qualitative analysis of nonautonomous second order

differential equation In mathematics, a differential equation is an equation that relates one or more unknown functions and their derivatives. In applications, the functions generally represent physical quantities, the derivatives represent their rates of change, an ...

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American people, American mathematician, electrical engineering, electrical engineer, and cryptography, cryptographer known as a "father of information theory". As a 21-year-o ...

used symbolic sequences and shifts of finite type in his 1948 paper ''

A mathematical theory of communication "A Mathematical Theory of Communication" is an article by mathematician Claude E. Shannon published in ''Bell System Technical Journal'' in 1948. It was renamed ''The Mathematical Theory of Communication'' in the 1949 book of the same name, a sma ...

'' that gave birth to

information theory Information theory is the scientific study of the quantification (science), quantification, computer data storage, storage, and telecommunication, communication of information. The field was originally established by the works of Harry Nyquist a ...

. During the late 1960s the method of symbolic dynamics was developed to hyperbolic toral automorphisms by Roy Adler and Benjamin Weiss, and to Anosov diffeomorphisms by

Yakov Sinai Yakov Grigorevich Sinai (russian: link=no, Я́ков Григо́рьевич Сина́й; born September 21, 1935) is a Russian-American mathematician known for his work on dynamical systems. He contributed to the modern metric theory of dy ...

who used the symbolic model to construct

Gibbs measure In mathematics, the Gibbs measure, named after Josiah Willard Gibbs, is a probability measure frequently seen in many problems of probability theory and statistical mechanics. It is a generalization of the canonical ensemble to infinite systems. Th ...

s. In the early 1970s the theory was extended to Anosov flows by

Marina Ratner Marina Evseevna Ratner (russian: Мари́на Евсе́евна Ра́тнер; October 30, 1938 – July 7, 2017) was a professor of mathematics at the University of California, Berkeley who worked in ergodic theory. Around 1990, she proved ...

, and to Axiom A diffeomorphisms and flows by Rufus Bowen. A spectacular application of the methods of symbolic dynamics is

Sharkovskii's theorem In mathematics, Sharkovskii's theorem, named after Oleksandr Mykolaiovych Sharkovskii, who published it in 1964, is a result about discrete dynamical systems. One of the implications of the theorem is that if a discrete dynamical system on the r ...

about

periodic orbit In mathematics, in the study of iterated functions and dynamical systems, a periodic point of a function is a point which the system returns to after a certain number of function iterations or a certain amount of time. Iterated functions Given a ...

s of a

continuous map In mathematics, a continuous function is a function such that a continuous variation (that is a change without jump) of the argument induces a continuous variation of the value of the function. This means that there are no abrupt changes in valu ...

of an interval into itself (1964).

Examples

Concepts such as

heteroclinic orbit In mathematics, in the phase portrait of a dynamical system, a heteroclinic orbit (sometimes called a heteroclinic connection) is a path in phase space which joins two different equilibrium points. If the equilibrium points at the start and end o ...

s and homoclinic orbits have a particularly simple representation in symbolic dynamics.

Itinerary

Itinerary of point with respect to the partition is a sequence of symbols. It describes dynamic of the point. Mathematics of Complexity and Dynamical Systems by Robert A. Meyers. Springer Science & Business Media, 2011, , 9781461418054

Applications

Symbolic dynamics originated as a method to study general dynamical systems; now its techniques and ideas have found significant applications in

data storage Data storage is the recording (storing) of information (data) in a storage medium. Handwriting, phonographic recording, magnetic tape, and optical discs are all examples of storage media. Biological molecules such as RNA and DNA are conside ...

and transmission,

linear algebra Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrices. ...

, the motions of the planets and many other areas. The distinct feature in symbolic dynamics is that time is measured in ''

discrete Discrete may refer to: *Discrete particle or quantum in physics, for example in quantum theory *Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit *Discrete group, a g ...

'' intervals. So at each time interval the system is in a particular ''state''. Each state is associated with a symbol and the evolution of the system is described by an infinite

of symbols—represented effectively as

strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...

. If the system states are not inherently discrete, then the state vector must be discretized, so as to get a

coarse-grained Granularity (also called graininess), the condition of existing in granules or grains, refers to the extent to which a material or system is composed of distinguishable pieces. It can either refer to the extent to which a larger entity is sub ...

description of the system.

References

External links

ChaosBook.org
Chapter "Transition graphs" Dynamical systems Combinatorics on words